package com.hc.programming.string;

import java.util.Arrays;

/**
 * 给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
 * <p>
 * 示例 1:
 * 输入: s = "abab"
 * 输出: true
 * 解释: 可由子串 "ab" 重复两次构成。
 * 示例 2:
 * 输入: s = "aba"
 * 输出: false
 * 示例 3:
 * 输入: s = "abcabcabcabc"
 * 输出: true
 * 解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)
 * <p>
 * 提示：
 * 1 <= s.length <= 10^4
 * s 由小写英文字母组成
 *
 * @author huangchao E-mail:fengquan8866@163.com
 * @version 创建时间：2024/10/29 20:16
 */
public class 重复的子字符串 {

    public static void main(String[] args) {
        System.out.println(repeatedSubstringPattern("abab") + "----=true");
        System.out.println(repeatedSubstringPattern("aba") + "----=false");
        System.out.println(repeatedSubstringPattern("abcabcabcabc") + "----=true");
        System.out.println(repeatedSubstringPattern("abac") + "----=false");
        System.out.println(repeatedSubstringPattern("babbbbaabb") + "----=false");
        System.out.println(repeatedSubstringPattern("aabaabaab") + "----=true");
        System.out.println(repeatedSubstringPattern("abaabaaba") + "----=true");
    }

    public static boolean repeatedSubstringPattern(String s) {
        return 移动匹配(s);
//        return kmp(s);
    }

    private static boolean kmp(String s) {
        char[] chars = s.toCharArray();
        int[] next = new int[chars.length];
        int i = 1, j = 0;
        next[0] = 0;
        while (i < chars.length) {
            while (j > 0 && chars[i] != chars[j]) {
                j = next[j - 1];
            }
            if (chars[i] == chars[j]) {
                j++;
            }
            next[i++] = j;
        }
        System.out.println(Arrays.toString(next));

        return next[chars.length - 1] > 0 && next[chars.length - 1] % (chars.length - next[chars.length - 1]) == 0;
    }

    private static boolean 移动匹配(String s) {
        char[] chars = s.toCharArray();
        for (int i = chars.length / 2; i > 0; i--) {
            // 找到 = chars[0] 的节点，&& 长度为 i 的倍数，否则不可能重复
            if (chars[i] == chars[0] && chars.length % i == 0) {
                boolean flag = true;
                // 分段匹配
                for (int j = chars.length; j > i; j -= i) {
                    // 匹配
                    for (int k = j - i; k < j; k++) {
                        if (chars[k] != chars[k - i]) {
                            flag = false;
                            break;
                        }
                    }
                    if (!flag) break;
                }
                if (flag) return true;
            }
        }
        return false;
    }
}
